{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "<center>\n",
    "<img src=\"https://github.com/oussou-dev/mlcourse.ai/blob/jupyter_french/img/ods_stickers.jpg?raw=true\" />\n",
    "    \n",
    "<br> \n",
    "       \n",
    "<div style=\"font-weight:700;font-size:25px\"> [mlcourse.ai](https://mlcourse.ai) - Open Machine Learning Course  </div>    \n",
    "    \n",
    "<br>    \n",
    "Auteur: [Pavel Nesterov](http://pavelnesterov.info/). Traduit et édité par [Christina Butsko](https://www.linkedin.com/in/christinabutsko/), [Yury Kashnitsky](https://yorko.github.io), [Nerses Bagiyan](https://www.linkedin.com/in/nersesbagiyan/), [Yulia Klimushina](https://www.linkedin.com/in/yuliya-klimushina-7168a9139), [Yuanyuan Pao](https://www.linkedin.com/in/yuanyuanpao/) et [Ousmane Cissé](https://github.com/oussou-dev). Ce matériel est soumis aux termes et conditions de la licence [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). L'utilisation gratuite est autorisée à des fins non commerciales."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "# <center>Topic 4. Classification et régression linéaires\n",
    "\n",
    "\n",
    "\n",
    "## <center> Part1. Moindres carrés ordinaires\n",
    "\n",
    "Nous allons commencer à étudier les modèles linéaires avec régression linéaire. Tout d'abord, vous devez spécifier un modèle qui relie la variable dépendante $y$ aux facteurs explicatifs (ou caractéristiques); pour les modèles linéaires, la fonction de dépendance prendra la forme suivante: $y = w_0 + \\sum_{i=1}^m w_i x_i$. Si nous ajoutons une dimension fictive $x_0 = 1$ (c’est-à-dire un biais) pour chaque observation, la forme linéaire peut être réécrite de manière légèrement plus compacte en tirant le terme absolu $w_0$ dans la somme $y = \\sum_{i=0}^m w_i x_i = \\textbf{w}^\\text{T} \\textbf{x}$. Si nous avons une matrice d'observations d'entités, où les lignes sont des observations provenant d'un ensemble de données, nous devons ajouter une seule colonne à gauche. Nous définissons le modèle comme suit:\n",
    "\n",
    "$$\\large \\textbf y = \\textbf X \\textbf w + \\epsilon,$$\n",
    "\n",
    "où\n",
    "\n",
    "- $\\textbf y \\in \\mathbb{R}^n$ - est la variable dépendante (ou cible);\n",
    "- $w$ - est le vecteur des paramètres du modèle (dans l'apprentissage automatique, ces paramètres sont souvent appelés pondérations);\n",
    "- $\\textbf X$ - est une matrice d'observations et de leurs caractéristiques, $n $ dimensionnée en rangées par colonnes $m + 1 $ (y compris la colonne fictive de gauche) avec rang complet par colonnes: $\\text{rank}\\left(\\textbf X\\right) = m + 1 $;\n",
    "- $\\epsilon $ - une variable correspondant à l'erreur de modèle aléatoire et imprévisible.\n",
    "\n",
    "Nous pouvons aussi écrire cette expression pour chaque observation\n",
    "\n",
    "$$\\large y_i = \\sum_{j=0}^m w_j X_{ij} + \\epsilon_i$$\n",
    "\n",
    "Les restrictions suivantes sont également appliquées au modèle (sinon, ce sera une autre sorte de régression que linéaire):\n",
    "\n",
    "- l'espérance d'erreurs aléatoires est égale à zéro: $\\forall i: \\mathbb{E}\\left[\\epsilon_i\\right] = 0 $;\n",
    "- l'erreur aléatoire a la même variance finie, cette propriété est appelée <a href=\"https://en.wikipedia.org/wiki/Homoscedasticity\">homoscédasticité</a>: $\\forall i: \\text{Var}\\left(\\epsilon_i\\right) = \\sigma^2 < \\infty $;\n",
    "- les erreurs aléatoires ne sont pas corrélées: $\\forall i \\neq j: \\text{Cov}\\left(\\epsilon_i, \\epsilon_j\\right) = 0 $.\n",
    "\n",
    "Est. $\\widehat{w}_i $ des poids $w_i $ est appelé linéaire si\n",
    "\n",
    "$$\\large \\widehat{w}_i = \\omega_{1i}y_1 + \\omega_{2i}y_2 + \\cdots + \\omega_{ni}y_n,$$\n",
    "\n",
    "où $\\forall\\ k\\ $, $\\omega_{ki} $\n",
    "ne dépend que des échantillons de $X $ et presque certainement de manière non linéaire. Puisque la solution pour trouver les poids optimaux est une estimation linéaire, le modèle s'appelle *régression linéaire*. Introduisons une autre définition. L'estimation $\\widehat{w}_i $ est appelée non biaisée lorsque ses attentes sont égales à la valeur réelle mais inconnue du paramètre estimé:\n",
    "\n",
    "$$\\Large \\mathbb{E}\\left[\\widehat{w}_i\\right] = w_i$$\n",
    "\n",
    "L'un des moyens de calculer ces pondérations consiste à utiliser la méthode des moindres carrés ordinaires (MCO), qui minimise l'erreur quadratique moyenne entre la valeur réelle de la variable dépendante et la valeur prédite donnée par le modèle:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl}\\mathcal{L}\\left(\\textbf X, \\textbf{y}, \\textbf{w} \\right) &=& \\frac{1}{2n} \\sum_{i=1}^n \\left(y_i - \\textbf{w}^\\text{T} \\textbf{x}_i\\right)^2 \\\\\n",
    "&=& \\frac{1}{2n} \\left\\| \\textbf{y} - \\textbf X \\textbf{w} \\right\\|_2^2 \\\\\n",
    "&=& \\frac{1}{2n} \\left(\\textbf{y} - \\textbf X \\textbf{w}\\right)^\\text{T} \\left(\\textbf{y} - \\textbf X \\textbf{w}\\right)\n",
    "\\end{array}$$\n",
    "\n",
    "Pour résoudre ce problème d'optimisation, nous devons calculer des dérivées par rapport aux paramètres du modèle. Nous les mettons à zéro et résolvons l'équation résultante pour $\\textbf w$ (la différenciation matricielle peut sembler difficile; essayez de le faire en termes de sommes pour être sûr de la réponse):\n",
    "\n",
    "Petit CheatSheet sur les dérivés de la matrice:\n",
    "\n",
    "\n",
    "\n",
    "$$\\large \\begin{array}{rcl} \n",
    "\\frac{\\partial}{\\partial \\textbf{X}} \\textbf{X}^{\\text{T}} \\textbf{A} &=& \\textbf{A} \\\\\n",
    "\\frac{\\partial}{\\partial \\textbf{X}} \\textbf{X}^{\\text{T}} \\textbf{A} \\textbf{X} &=& \\left(\\textbf{A} + \\textbf{A}^{\\text{T}}\\right)\\textbf{X} \\\\\n",
    "\\frac{\\partial}{\\partial \\textbf{A}} \\textbf{X}^{\\text{T}} \\textbf{A} \\textbf{y} &=&  \\textbf{X}^{\\text{T}} \\textbf{y}\\\\\n",
    "\\frac{\\partial}{\\partial \\textbf{X}} \\textbf{A}^{-1} &=& -\\textbf{A}^{-1} \\frac{\\partial \\textbf{A}}{\\partial \\textbf{X}} \\textbf{A}^{-1} \n",
    "\\end{array}$$\n",
    "\n",
    "Continuons:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \\frac{\\partial \\mathcal{L}}{\\partial \\textbf{w}} &=& \\frac{\\partial}{\\partial \\textbf{w}} \\frac{1}{2n} \\left( \\textbf{y}^{\\text{T}} \\textbf{y} -2\\textbf{y}^{\\text{T}} \\textbf{X} \\textbf{w} + \\textbf{w}^{\\text{T}} \\textbf{X}^{\\text{T}} \\textbf{X} \\textbf{w}\\right) \\\\\n",
    "&=& \\frac{1}{2n} \\left(-2 \\textbf{X}^{\\text{T}} \\textbf{y} + 2\\textbf{X}^{\\text{T}} \\textbf{X} \\textbf{w}\\right)\n",
    "\\end{array}$$\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \\frac{\\partial \\mathcal{L}}{\\partial \\textbf{w}} = 0 &\\Leftrightarrow& \\frac{1}{2n} \\left(-2 \\textbf{X}^{\\text{T}} \\textbf{y} + 2\\textbf{X}^{\\text{T}} \\textbf{X} \\textbf{w}\\right) = 0 \\\\\n",
    "&\\Leftrightarrow& -\\textbf{X}^{\\text{T}} \\textbf{y} + \\textbf{X}^{\\text{T}} \\textbf{X} \\textbf{w} = 0 \\\\\n",
    "&\\Leftrightarrow& \\textbf{X}^{\\text{T}} \\textbf{X} \\textbf{w} = \\textbf{X}^{\\text{T}} \\textbf{y} \\\\\n",
    "&\\Leftrightarrow& \\textbf{w} = \\left(\\textbf{X}^{\\text{T}} \\textbf{X}\\right)^{-1} \\textbf{X}^{\\text{T}} \\textbf{y}\n",
    "\\end{array}$$\n",
    "\n",
    "En tenant compte de toutes les définitions et conditions décrites ci-dessus, nous pouvons dire que, sur la base du théorème de <a href=\"https://en.wikipedia.org/wiki/Gauss–Markov_theorem\">Gauss – Markov</a>, les estimateurs MLS des paramètres du modèle sont optimaux pour tous les estimateurs linéaires et non biaisés, c'est-à-dire qu'ils donnent la variance la plus faible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Estimation de vraisemblance maximale\n",
    "\n",
    "On pourrait se demander pourquoi nous choisissons de minimiser l’erreur quadratique moyenne au lieu d’autre chose? Après tout, on peut minimiser la valeur absolue moyenne du résidu. La seule chose qui se produira, si nous modifions la valeur minimisée, est que nous dépasserons les conditions du théorème de Gauss-Markov et nos estimations cesseront donc d'être optimales par rapport aux conditions linéaires et non biaisées.\n",
    "\n",
    "Avant de continuer, voyons maintenant l’estimation du maximum de vraisemblance avec un exemple simple.\n",
    "\n",
    "Beaucoup de gens se souviennent probablement de la formule de l'alcool éthylique, alors j'ai décidé de faire une expérience pour déterminer si les gens se souvenaient d'une formule plus simple pour le méthanol: $CH_3OH$. Nous avons interrogé 400 personnes et constaté que seules 117 personnes se souvenaient de la formule. Ensuite, il est raisonnable de supposer que la probabilité que le prochain répondant connaisse la formule de l'alcool méthylique est $\\frac{117}{400} \\approx 29\\%$. Montrons que cette évaluation intuitive est non seulement bonne, mais aussi une estimation du maximum de vraisemblance. D'où vient cette estimation? Rappelez-vous la définition de la distribution de Bernoulli: une variable aléatoire a une distribution <a href=\"https://en.wikipedia.org/wiki/Bernoulli_distribution\"> Bernoulli</a> si elle ne prend que deux valeurs ($1$ et $0$ avec la probabilité $\\theta$ et $1 - \\theta$, respectivement) et a la fonction de distribution de probabilité suivante:\n",
    "\n",
    "$$\\Large p\\left(\\theta, x\\right) = \\theta^x \\left(1 - \\theta\\right)^\\left(1 - x\\right), x \\in \\left\\{0, 1\\right\\}$$\n",
    "\n",
    "Cette distribution est exactement ce dont nous avons besoin, et le paramètre de distribution $\\theta$ est l'estimation de la probabilité qu'une personne connaisse la formule de l'alcool méthylique. Dans nos $400$ expériences *indépendantes*, désignons leurs résultats par $\\textbf{x} = \\left(x_1, x_2, \\ldots, x_{400}\\right)$. Écrivons la vraisemblance de nos données (observations), c'est-à-dire la probabilité d'observer exactement ces 117 réalisations de la variable aléatoire $x = 1$ et 283 réalisations de $x = 0$:\n",
    "\n",
    "$$\\Large p(\\textbf{x}; \\theta) = \\prod_{i=1}^{400} \\theta^{x_i} \\left(1 - \\theta\\right)^{\\left(1 - x_i\\right)} = \\theta^{117} \\left(1 - \\theta\\right)^{283}$$\n",
    "\n",
    "Ensuite, nous allons maximiser l’expression par rapport à $\\theta$. Le plus souvent, cela ne se fait pas avec la probabilité $p(\\textbf{x}; \\theta)$ mais avec son logarithme (la transformation monotone ne change pas la solution mais simplifie grandement le calcul):\n",
    "\n",
    "$$\\Large \\log p(\\textbf{x}; \\theta) = \\log \\prod_{i=1}^{400} \\theta^{x_i} \\left(1 - \\theta\\right)^{\\left(1 - x_i\\right)} = $$\n",
    "$$ \\large = \\log \\theta^{117} \\left(1 - \\theta\\right)^{283} =  117 \\log \\theta + 283 \\log \\left(1 - \\theta\\right)$$\n",
    "\n",
    "Maintenant, nous voulons trouver une telle valeur de $\\theta$ qui maximisera la probabilité. Pour cela, prenons la dérivée par rapport à $\\theta$, fixons-la à zéro et résolvons l'équation résultante:\n",
    "\n",
    "$$\\Large  \\frac{\\partial \\log p(\\textbf{x}; \\theta)}{\\partial \\theta} = \\frac{\\partial}{\\partial \\theta} \\left(117 \\log \\theta + 283 \\log \\left(1 - \\theta\\right)\\right) = \\frac{117}{\\theta} - \\frac{283}{1 - \\theta};$$\n",
    "\n",
    "Il s’avère que notre évaluation intuitive correspond exactement à l’estimation du maximum de vraisemblance. Appliquons maintenant le même raisonnement au problème de la régression linéaire et essayons de déterminer ce qui se situe au-delà de l’erreur quadratique moyenne. Pour ce faire, nous devrons examiner la régression linéaire du point de vue probabiliste. Notre modèle reste naturellement le même:\n",
    "\n",
    "$$\\Large \\textbf y = \\textbf X \\textbf w + \\epsilon,$$\n",
    "\n",
    "mais supposons maintenant que les erreurs aléatoires suivent une distribution <a href=\"https://en.wikipedia.org/wiki/Normal_distribution\">Normale centrée</a> :\n",
    "\n",
    "$$\\Large \\epsilon_i \\sim \\mathcal{N}\\left(0, \\sigma^2\\right)$$\n",
    "\n",
    "Réécrivons le modèle dans une nouvelle perspective:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "y_i &=& \\sum_{j=1}^m w_j X_{ij} + \\epsilon_i \\\\\n",
    "&\\sim& \\sum_{j=1}^m w_j X_{ij} + \\mathcal{N}\\left(0, \\sigma^2\\right) \\\\\n",
    "p\\left(y_i \\mid \\textbf X; \\textbf{w}\\right) &=& \\mathcal{N}\\left(\\sum_{j=1}^m w_j X_{ij}, \\sigma^2\\right)\n",
    "\\end{array}$$\n",
    "\n",
    "Puisque les exemples sont pris indépendamment (les erreurs non corrélées sont l’une des conditions du théorème de Gauss-Markov), il est donc vraisemblable que les données ressembleront à un produit des fonctions de densité $p\\left(y_i\\right)$. Considérons le log-vraisemblance, qui nous permet de passer des produits à des sommes:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\log p\\left(\\textbf{y}\\mid \\textbf X; \\textbf{w}\\right) &=& \\log \\prod_{i=1}^n \\mathcal{N}\\left(\\sum_{j=1}^m w_j X_{ij}, \\sigma^2\\right) \\\\\n",
    "&=& \\sum_{i=1}^n \\log \\mathcal{N}\\left(\\sum_{j=1}^m w_j X_{ij}, \\sigma^2\\right) \\\\\n",
    "&=& -\\frac{n}{2}\\log 2\\pi\\sigma^2 -\\frac{1}{2\\sigma^2} \\sum_{i=1}^n \\left(y_i - \\textbf{w}^\\text{T} \\textbf{x}_i\\right)^2\n",
    "\\end{array}$$\n",
    "\n",
    "Nous voulons trouver l'hypothèse du maximum de vraisemblance, c'est-à-dire que nous devons maximiser l'expression $p\\left(\\textbf{y} \\mid \\textbf X; \\textbf{w}\\right)$ pour obtenir $\\textbf{w}_{\\text{ML}}$, ce qui revient à maximiser son logarithme. Notez que, tout en maximisant la fonction sur un paramètre, vous pouvez supprimer tous les membres qui ne dépendent pas de ce paramètre:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\textbf{w}_{\\text{ML}} &=& \\arg \\max_{\\textbf w} p\\left(\\textbf{y}\\mid \\textbf X; \\textbf{w}\\right) = \\arg \\max_{\\textbf w} \\log p\\left(\\textbf{y}\\mid \\textbf X; \\textbf{w}\\right)\\\\\n",
    "&=& \\arg \\max_{\\textbf w} -\\frac{n}{2}\\log 2\\pi\\sigma^2 -\\frac{1}{2\\sigma^2} \\sum_{i=1}^n \\left(y_i - \\textbf{w}^{\\text{T}} \\textbf{x}_i\\right)^2 \\\\\n",
    "&=& \\arg \\max_{\\textbf w} -\\frac{1}{2\\sigma^2} \\sum_{i=1}^n \\left(y_i - \\textbf{w}^{\\text{T}} \\textbf{x}_i\\right)^2 \\\\\n",
    "&=&  \\arg \\min_{\\textbf w} \\mathcal{L}\\left(\\textbf X, \\textbf{y}, \\textbf{w} \\right)\n",
    "\\end{array}$$\n",
    "\n",
    "Ainsi, nous avons vu que la maximisation de la probabilité des données est la même que la minimisation de l'erreur quadratique moyenne (compte tenu des hypothèses ci-dessus). Il s'avère qu'une telle fonction de coût est une conséquence du fait que les erreurs sont distribuées normalement."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Décomposition biais-variance\n",
    "\n",
    "Parlons un peu des propriétés d'erreur de la prédiction par régression linéaire (en fait, cette discussion est valable pour tous les algorithmes d'apprentissage automatique). Nous venons de couvrir les points suivants:\n",
    "\n",
    "- la vraie valeur de la variable cible est la somme d'une fonction déterministe $f\\left(\\textbf{x}\\right)$ et d'une erreur aléatoire $\\epsilon$: $y = f\\left(\\textbf{x}\\right) + \\epsilon$;\n",
    "- l'erreur est normalement distribuée avec une moyenne nulle et une certaine variance: $\\epsilon \\sim \\mathcal{N}\\left(0, \\sigma^2\\right)$;\n",
    "- la vraie valeur de la variable cible est aussi normalement distribuée: $y \\sim \\mathcal{N}\\left(f\\left(\\textbf{x}\\right), \\sigma^2\\right)$;\n",
    "- nous essayons d'approximer une fonction déterministe mais inconnue $f\\left(\\textbf{x}\\right)$ en utilisant une fonction linéaire des covariables $\\widehat{f}\\left(\\textbf{x}\\right)$, qui est à son tour une estimation ponctuelle de la fonction $f$ dans l'espace des fonctions (plus précisément, la famille de fonctions linéaires que nous avons limitée à notre espace), c’est-à-dire une variable aléatoire qui a la moyenne et la variance.\n",
    "\n",
    "Donc, l'erreur au point $\\textbf{x}$ se décompose comme suit:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\text{Err}\\left(\\textbf{x}\\right) &=& \\mathbb{E}\\left[\\left(y - \\widehat{f}\\left(\\textbf{x}\\right)\\right)^2\\right] \\\\\n",
    "&=& \\mathbb{E}\\left[y^2\\right] + \\mathbb{E}\\left[\\left(\\widehat{f}\\left(\\textbf{x}\\right)\\right)^2\\right] - 2\\mathbb{E}\\left[y\\widehat{f}\\left(\\textbf{x}\\right)\\right] \\\\\n",
    "&=& \\mathbb{E}\\left[y^2\\right] + \\mathbb{E}\\left[\\widehat{f}^2\\right] - 2\\mathbb{E}\\left[y\\widehat{f}\\right] \\\\\n",
    "\\end{array}$$\n",
    "\n",
    "Pour plus de clarté, nous omettrons la notation de l'argument des fonctions. Considérons chaque membre séparément. Les deux premiers sont facilement décomposables selon la formule $\\text{Var}\\left(z\\right) = \\mathbb{E}\\left[z^2\\right] - \\mathbb{E}\\left[z\\right]^2$:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\mathbb{E}\\left[y^2\\right] &=& \\text{Var}\\left(y\\right) + \\mathbb{E}\\left[y\\right]^2 = \\sigma^2 + f^2\\\\\n",
    "\\mathbb{E}\\left[\\widehat{f}^2\\right] &=& \\text{Var}\\left(\\widehat{f}\\right) + \\mathbb{E}\\left[\\widehat{f}\\right]^2 \\\\\n",
    "\\end{array}$$\n",
    "\n",
    "Notez que:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\text{Var}\\left(y\\right) &=& \\mathbb{E}\\left[\\left(y - \\mathbb{E}\\left[y\\right]\\right)^2\\right] \\\\\n",
    "&=& \\mathbb{E}\\left[\\left(y - f\\right)^2\\right] \\\\\n",
    "&=& \\mathbb{E}\\left[\\left(f + \\epsilon - f\\right)^2\\right] \\\\\n",
    "&=& \\mathbb{E}\\left[\\epsilon^2\\right] = \\sigma^2\n",
    "\\end{array}$$\n",
    "\n",
    "$$\\Large \\mathbb{E}[y] = \\mathbb{E}[f + \\epsilon] = \\mathbb{E}[f] + \\mathbb{E}[\\epsilon] = f$$\n",
    "\n",
    "Et finalement, nous arrivons au dernier terme de la somme. Rappelons que l'erreur et la variable cible sont indépendantes l'une de l'autre:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\mathbb{E}\\left[y\\widehat{f}\\right] &=& \\mathbb{E}\\left[\\left(f + \\epsilon\\right)\\widehat{f}\\right] \\\\\n",
    "&=& \\mathbb{E}\\left[f\\widehat{f}\\right] + \\mathbb{E}\\left[\\epsilon\\widehat{f}\\right] \\\\\n",
    "&=& f\\mathbb{E}\\left[\\widehat{f}\\right] + \\mathbb{E}\\left[\\epsilon\\right] \\mathbb{E}\\left[\\widehat{f}\\right]  = f\\mathbb{E}\\left[\\widehat{f}\\right]\n",
    "\\end{array}$$\n",
    "\n",
    "Enfin, rassemblons tout cela:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\text{Err}\\left(\\textbf{x}\\right) &=& \\mathbb{E}\\left[\\left(y - \\widehat{f}\\left(\\textbf{x}\\right)\\right)^2\\right] \\\\\n",
    "&=& \\sigma^2 + f^2 + \\text{Var}\\left(\\widehat{f}\\right) + \\mathbb{E}\\left[\\widehat{f}\\right]^2 - 2f\\mathbb{E}\\left[\\widehat{f}\\right] \\\\\n",
    "&=& \\left(f - \\mathbb{E}\\left[\\widehat{f}\\right]\\right)^2 + \\text{Var}\\left(\\widehat{f}\\right) + \\sigma^2 \\\\\n",
    "&=& \\text{Bias}\\left(\\widehat{f}\\right)^2 + \\text{Var}\\left(\\widehat{f}\\right) + \\sigma^2\n",
    "\\end{array}$$\n",
    "\n",
    "Avec cela, nous avons atteint notre objectif ultime - la dernière formule nous dit que l'erreur de prévision de tout modèle de type $y = f\\left(\\textbf{x}\\right) + \\epsilon$ est composée de:\n",
    "\n",
    "- biais carré: $\\text{Bias}\\left(\\widehat{f}\\right)$ est l'erreur moyenne pour tous les ensembles de données;\n",
    "- variance: $\\text{Var}\\left(\\widehat{f}\\right)$ correspond à la variabilité d'erreur, ou en fonction de la variation d'erreur si nous entraînons le modèle à différents ensembles de données;\n",
    "- erreur inamovible: $\\sigma^2$.\n",
    "\n",
    "Bien que nous ne puissions rien faire avec le terme $\\sigma^2$, nous pouvons influencer les deux premiers. Idéalement, nous aimerions nier ces deux termes (carré supérieur gauche de l’image), mais, dans la pratique, il est souvent nécessaire d’équilibrer les estimations biaisées et instables (variance élevée).\n",
    "\n",
    "<img src=\"https://github.com/oussou-dev/mlcourse.ai/blob/jupyter_french/img/bvtf.png?raw=true\" width=\"480\">\n",
    "\n",
    "En règle générale, à mesure que le modèle devient plus informatisé (par exemple, lorsque le nombre de paramètres libres augmente), la variance (dispersion) de l'estimation augmente également, mais le biais diminue. Du fait que l'ensemble de formation est entièrement mémorisé au lieu d'être généralisé, de petites modifications entraînent des résultats inattendus (surapprentissage). D'un autre côté, si le modèle est trop faible, il ne sera pas en mesure d'apprendre le schéma, ce qui entraînera un apprentissage différent, compensé par la bonne solution.\n",
    "\n",
    "<img src=\"https://github.com/oussou-dev/mlcourse.ai/blob/jupyter_french/img/biasvariance.png?raw=true\" width=\"480\">\n",
    "\n",
    "Le théorème de Gauss-Markov affirme que l'estimateur MLO des paramètres du modèle linéaire est le meilleur pour la classe d'estimateur linéaire non biaisé. Cela signifie que s'il existe un autre modèle non biaisé $g$, appartenant à la même classe de modèles linéaires, nous pouvons être sûrs que $Var\\left(\\widehat{f}\\right) \\leq Var\\left(g\\right)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Régularisation de la régression linéaire\n",
    "\n",
    "Il existe des situations dans lesquelles nous pourrions augmenter intentionnellement le biais du modèle pour des raisons de stabilité, c'est-à-dire pour réduire la variance du modèle $\\text{Var}\\left(\\widehat{f}\\right)$. L'une des conditions du théorème de Gauss-Markov est le rang de colonne complet de la matrice $\\textbf{X}$. Sinon, la solution OLS    $\\textbf{w} = \\left(\\textbf{X}^\\text{T} \\textbf{X}\\right)^{-1} \\textbf{X}^\\text{T} \\textbf{y}$ n'existe pas car la matrice inverse $\\left(\\textbf{X}^\\text{T} \\textbf{X}\\right)^{-1}$ n'existe pas. En d'autres termes, la matrice $\\textbf{X}^\\text{T} \\textbf{X}$ sera singulière ou dégénérée. Ce problème s'appelle un <a href=\"https://en.wikipedia.org/wiki/Well-posed_problem\"> problème</a> mal posé. Des problèmes comme celui-ci doivent être corrigés, à savoir que la matrice $\\textbf{X}^\\text{T} \\textbf{X}$ doit devenir non dégénérée ou régulière (c'est pourquoi ce processus s'appelle régularisation). On observe souvent ce qu'on appelle la multicolinéarité dans les données: lorsque deux caractéristiques ou plus sont fortement corrélées, cela se manifeste dans la matrice $\\textbf{X}$ sous la forme d'une dépendance \"presque\" linéaire entre les colonnes. Par exemple, dans le problème de la prédiction du prix des logements en fonction de leurs paramètres, les attributs \"zone avec balcon\" et \"zone sans balcon\" auront une relation \"presque\" linéaire. Formellement, la matrice $\\textbf{X}^\\text{T} \\textbf{X}$ pour de telles données est réversible, mais, en raison de la multicolinéarité, certaines de ses valeurs propres seront proches de zéro. Dans la matrice inverse $\\textbf{X}^\\text{T} \\textbf{X}$, des valeurs propres extrêmement grandes apparaîtront, car les valeurs propres de la matrice inverse sont $\\frac{1}{\\lambda_i}$. Le résultat de cette vacillation des valeurs propres est une estimation instable des paramètres du modèle, c'est-à-dire que l'ajout d'un nouvel ensemble d'observations aux données d'apprentissage entraînera une solution complètement différente.\n",
    "Une méthode de régularisation est la régularisation de <a href=\"https://en.wikipedia.org/wiki/Tikhonov_regularization\">Tikhonov</a>, qui ressemble généralement à l’ajout d’un nouveau membre à l’erreur quadratique moyenne:\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\mathcal{L}\\left(\\textbf{X}, \\textbf{y}, \\textbf{w} \\right) &=& \\frac{1}{2n} \\left\\| \\textbf{y} - \\textbf{X} \\textbf{w} \\right\\|_2^2 + \\left\\| \\Gamma \\textbf{w}\\right\\|^2\\\\\n",
    "\\end{array}$$\n",
    "\n",
    "La matrice de Tikhonov est souvent exprimée par le produit d'un nombre par la matrice d'identité: $\\Gamma = \\frac{\\lambda}{2} E$. Dans ce cas, le problème de la minimisation de l'erreur quadratique moyenne devient un problème avec une restriction de la norme $L_2$. Si nous différencions la nouvelle fonction de coût par rapport aux paramètres du modèle, si nous définissons la fonction résultante à zéro et si nous réarrangons pour $\\textbf{w}$, nous obtenons la solution exacte du problème.\n",
    "\n",
    "$$\\Large \\begin{array}{rcl} \n",
    "\\textbf{w} &=& \\left(\\textbf{X}^{\\text{T}} \\textbf{X} + \\lambda \\textbf{E}\\right)^{-1} \\textbf{X}^{\\text{T}} \\textbf{y}\n",
    "\\end{array}$$\n",
    "\n",
    "Ce type de régression est appelé régression de crête. La crête est la matrice diagonale que nous ajoutons à la matrice $\\textbf{X}^\\text{T} \\textbf{X}$ pour obtenir une matrice régulière.\n",
    "\n",
    "<img src=\"https://github.com/oussou-dev/mlcourse.ai/blob/jupyter_french/img/ridge.png?raw=true\">\n",
    "\n",
    "Une telle solution réduit la dispersion mais devient biaisée car la norme du vecteur de paramètres est également minimisée, ce qui fait que la solution passe à zéro. Sur la figure ci-dessous, la solution MCO se trouve à l'intersection des lignes pointillées blanches. Les points bleus représentent différentes solutions de régression de crête. On peut constater qu'en augmentant le paramètre de régularisation $\\lambda$, nous décalons la solution vers zéro.\n",
    "\n",
    "\n",
    "<img src=\"https://github.com/oussou-dev/mlcourse.ai/blob/jupyter_french/img/l2.png?raw=true\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Ressources utiles\n",
    "- Main course [site](https://mlcourse.ai), [course repo](https://github.com/Yorko/mlcourse.ai), and YouTube [channel](https://www.youtube.com/watch?v=QKTuw4PNOsU&list=PLVlY_7IJCMJeRfZ68eVfEcu-UcN9BbwiX)\n",
    "- Medium [\"story\"](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-4-linear-classification-and-regression-44a41b9b5220) based on this notebook\n",
    "- Course materials as a [Kaggle Dataset](https://www.kaggle.com/kashnitsky/mlcourse)\n",
    "- If you read Russian: an [article](https://habrahabr.ru/company/ods/blog/323890/) on Habrahabr with ~ the same material. And a [lecture](https://youtu.be/oTXGQ-_oqvI) on YouTube\n",
    "- A nice and concise overview of linear models is given in the book [“Deep Learning”](http://www.deeplearningbook.org) (I. Goodfellow, Y. Bengio, and A. Courville).\n",
    "- Linear models are covered practically in every ML book. We recommend “Pattern Recognition and Machine Learning” (C. Bishop) and “Machine Learning: A Probabilistic Perspective” (K. Murphy).\n",
    "- If you prefer a thorough overview of linear model from a statistician’s viewpoint, then look at “The elements of statistical learning” (T. Hastie, R. Tibshirani, and J. Friedman).\n",
    "- The book “Machine Learning in Action” (P. Harrington) will walk you through implementations of classic ML algorithms in pure Python.\n",
    "- [Scikit-learn](http://scikit-learn.org/stable/documentation.html) library. These guys work hard on writing really clear documentation.\n",
    "- Scipy 2017 [scikit-learn tutorial](https://github.com/amueller/scipy-2017-sklearn) by Alex Gramfort and Andreas Mueller.\n",
    "- One more [ML course](https://github.com/diefimov/MTH594_MachineLearning) with very good materials.\n",
    "- [Implementations](https://github.com/rushter/MLAlgorithms) of many ML algorithms. Search for linear regression and logistic regression."
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  },
  "nbTranslate": {
   "displayLangs": [
    "*"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
